class Solution {
    // 暴力枚举
    public int mySqrt2(int x) {
        if (x == 0 || x == 1) { // 排除特殊情况
            return x;
        }
        for (long i = 1; i <= x; i++) {
            if (i * i == x) {
                return (int)i;
            } else if (i * i > x) {
                return (int)i-1;
            }
        }
        return -1; // 这里只是过审
    }

    // 二分查找
    public int mySqrt(int x) {
        if (x == 0 || x == 1) { // 排除特殊情况
            return x;
        }
        long left = 1;
        long right = x;
        // 最终的结果是向下取整的，即 <= 是合法区域的
        while (left < right) {
            long mid = left + (right-left+1) / 2;
            if (mid*mid > x) {
                right = mid-1;
            } else {
                left = mid;
            }
        }
        // 找到了
        return (int)left;
    }
}